/**
 * 动态规划-最少硬币找零问题：给出要找零的钱数，以及一些面额和对应限制数量，
 * 问哪种找零方法所需硬币个数最少。
 * @param coins 面额数组（单纯的面额，这里没有限制数量）
 * @param amount 找零的目标值（要找零的钱数）
 * 例如：美元的硬币面额：1, 5, 10, 25 （单位：分）
 * 要找零36分，只需一个1分、一个10分、一个25分即可，也就是3个硬币就可以了
 */
export function minCoinChange(coins: number[], amount: number) {
    // 将每个子问题的结果记忆化
    const cache: number[][] = [];
    // 找零金额是value，得到它对应最少找零结果
    const makeChange = (value: number): number[] => {
        // 无需找零，直接返回[]
        if (value <= 0) {
            return [];
        }
        // 当前子问题的结果已经存在于记忆化中了
        if (cache[value] != null) {
            return cache[value];
        }

        // 当前子问题的结果。例如[1, 1, 5]，找零7分需要两个1分、一个5分
        let min: number[] = [];
        // 依赖的子问题结果
        let newMin: number[];
        /*
            在当前找零金额value下，把每个面额作为当前视角，去计算该面额的找零加上剩余
            金额下的最优找零，最后得到这几个视角里最优的那一项；也就是在当前找零金额下
            各种组合的解中取一个最优的。
        */
        for (let i = 0, cl = coins.length; i < cl; i ++) {
            // 当前面额
            const coin = coins[i];
            // 当前面额所依赖的子问题（剩余找零金额）
            const newAmount = value - coin;
            // 剩余找零金额为0，证明当前面额正好够找零，也是当前找零金额value下最优解，可直接break
            if (newAmount === 0) {
                min = [coin];
                break;
            } else if (newAmount > 0) {
                // 剩余找零金额大于0，要求出它的最少找零解
                newMin = makeChange(newAmount);
                // 连接当前面额和剩余找零金额的解，也就是当前视角下总的解
                const currMin = [coin].concat(newMin);
                if (
                    !!newMin.length // newMin必须要有解，因为必须达到那个找零钱数，而“背包问题”是不超过那个容量就行
                    && (!min.length || currMin.length < min.length) // 如果当前解比之前的解还优
                ) {
                    // 只留下当前找零金额下各种组合中最优的那个
                    min = [coin].concat(newMin);
                    // console.log('new Min ' + min + ' for ' + amount);
                }
            }
        }
        // 记忆化当前找零金额下的最优解
        cache[value] = min;
        return min;
    };
    return makeChange(amount);
}
